//============================================================================
// Name        : BinarySearchDeformation.cpp
// Author      : Xubin
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//小米科技笔试题
//有一个数组（单调不减），旋转了不知道多少个位，在该数组中找一个数的下标。写出代码（用C/c++或者java）
//并分析时间空间复杂度，考虑效率（很重要）。（本人认为可以采用改进的折中查找法）
//eg：数组 [6,7,1,2,3,4,4] 找3，返回4；
//函数原型
//C/C++：
//int find(int * a,int n,int count) count为a数组长度;n为要查找的数
//============================================================================

#include <iostream>
#include <vector>
using namespace std;
typedef vector<short> VT;

void swap(short &i, short &j)
{
	short temp;
	temp = i;
	i = j;
	j = temp;
}

VT init_vector(short vecLen)
{
	VT v;
	short i;
	for (i = 0; i < vecLen; i++)
	{
		v.push_back(i);
	}
	return v;
}

void rotate_vector(VT &v, short len)
{
	len = len % (v.size());
	short low_l, high_l, low_r, high_r;
	low_l = 0;
	high_l = len - 1;
	low_r = len;
	high_r = v.size() - 1;

	short i, j;
	i = low_l, j = high_l;
	while (i < j)
	{
		swap(v[i], v[j]);
		i++, j--;
	}
	i = low_r, j = high_r;
	while (i < j)
	{
		swap(v[i], v[j]);
		i++, j--;
	}
	i = low_l, j = high_r;
	while (i < j)
	{
		swap(v[i], v[j]);
		i++, j--;
	}
}

//左闭右开区间！！！  [begin, end)
short find(const VT &v, short begin, short end, short toFind)
{
	cout << "  (" << begin << ", " << end << ")";
	if (begin + 1 == end)
	{
		if (v[begin] == toFind)
			return begin;
		else
			return -1;
	}

	short middle = begin + (end - begin) / 2;
	cout << "  mid:" << middle << endl;
	if (v[begin] < v[middle]) // mono, fist half
	{
		if (toFind >= v[begin] && toFind < v[middle])
		{
			return find(v, begin, middle, toFind);
		}
		else
		{
			return find(v, middle, end, toFind);
		}
	}
	else if (v[begin] == v[middle])
	{	//判断是否相等，是因为有可能整个串中出现多个相等的情况，这样就没法判断到底
		//是前半部分单调还是后半部分单调，因此前后两部分都可能要试
		short retVal;
		retVal = find(v, begin, middle, toFind);
		if (retVal < 0)
		{
			retVal = find(v, middle, end, toFind);
		}
		return retVal;
	}
	else
	{
		if (toFind >= v[middle] && toFind <= v[end - 1])
		{
			return find(v, middle, end, toFind);
		}
		else
		{
			return find(v, begin, middle, toFind);
		}
	}
}

void display(const VT &v)
{
	cout << ">>Display:";
	for (unsigned short i = 0; i < v.size(); i++)
	{
		cout << v[i] << ", ";
	}
	cout << endl;
}

int main()
{
	short toFind = 8;
	short position = -1;
	short distance = 0;
	VT v;
	//	v = init_vector(vecLen);
	v = VT(10,5);
	v[9] = 8;

	display(v);
	rotate_vector(v, distance);
	display(v);
	position = find(v, 0, v.size(), toFind);
	cout << "--------------Position" << position << endl;
}
